/*
 * Copyright (C) 2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define dfa_undef_object		efixnum(-1)
#define zmsk				thr_zr
#define lt_p(rule)			(rule)->data.bits.lt
#define eq_p(rule)			(rule)->data.bits.eq
#define gt_p(rule)			(rule)->data.bits.gt
#define word_p(rule)			(rule)->data.word

/*
 * Prototypes
 */
static void
dfa_init(elabel_t *label);

static void
dfa_value_push(east_node_t *node);

static void
dfa_value_pop(eint32_t count);

static edfa_rule_t **
dfa_get_rule_pool(eint32_t length);

static ehash_t **
dfa_get_hash_pool(eint32_t length);

static void
dfa_collect_rules(ehash_t *hash);

static void
dfa_collect_symbols(evector_t *vector);

static edfa_rule_t *
dfa_get_rule(void);

static ehash_t *
dfa_get_hash(void);

static void
dfa_eval(edfa_rule_t *rule);

static void
dfa_eval_rules(ehash_t *hash);

static void
dfa_eval_symbols(evector_t *vector, empz_t mask);

static void
dfa_ior_rules(ehash_t *dst_hash, ehash_t *src_hash);

static void
dfa_ior_symbols(elabel_t *label, evector_t *dst_vector, evector_t *src_vector);

static void
dfa_clear(evector_t *vector, eint32_t bit);

static void
dfa_undef(evector_t *vector, eint32_t bit);

static void
dfa_define(evector_t *vector, eint32_t bit);

static void
dfa_invalidate(evector_t *vector, evector_t *offsets);

static edfa_rule_t *
dfa_create_rule(evector_t *vector, eint32_t offset, eobject_t value);

static eobject_t
dfa_canonicalize(east_node_t *node);

static ebool_t
dfa_rule_set(evector_t *vector, east_node_t *name, east_node_t *value);

static ebool_t
dfa_add_rule(elabel_t *label, evector_t *vector,
	     east_node_t *name, east_node_t *value, eint32_t code);

static ebool_t
dfa_add_rule_cond(elabel_t *label, evector_t *vector,
		  east_node_t *name, east_node_t *value,
		  ecode_t code, ebool_t cond, ebool_t swap);

static void
dfa_rule_bool(elabel_t *label, east_node_t *node,
	      ecode_t code, east_node_t *jump);

static void
dfa_rule_cond(elabel_t *label, east_node_t *lnode, east_node_t *rnode,
	      ecode_t code, east_node_t *jump);

static void
dfa_rule_table(elabel_t *label, east_node_t *name, ehash_t *table);

static void
dfa_body(elabel_t *label);

static void
dfa(elabel_t *label);

/*
 * Initialization
 */
static evector_t	 *dfa_root;

/* current dfa parsing state */
static evector_t	 *dfa_data;

/* values in stack expression stack */
static east_node_t	**dfa_value;
static evector_t	 *dfa_value_vector;

/* symbols that may change on function calls or store to pointee */
static eint32_t		 *dfa_changes;
static evector_t	 *dfa_changes_vector;
static eint32_t		 *dfa_escapes;
static evector_t	 *dfa_escapes_vector;

/* pool of objects to avoid/reduce gc calls */
static evector_t	 *dfa_rule_pool;
static evector_t	 *dfa_hash_pool;

/*
 * Implemenation
 */
void
init_dfa(void)
{
    eobject_t		*root;

    evector(&dfa_root, t_void, 6, 1);
    eadd_root((eobject_t *)&dfa_root);
    root = dfa_root->v.ptr;

    evector(&dfa_data, t_void, 16, 1);
    root[0] = dfa_data;

    evector(&dfa_value_vector, t_void, 16, 1);
    root[1] = dfa_value_vector;
    dfa_value = dfa_value_vector->v.obj;

    evector(&dfa_rule_pool, t_void, 16, 1);
    root[2] = dfa_rule_pool;

    evector(&dfa_hash_pool, t_void, 16, 1);
    root[3] = dfa_hash_pool;

    evector(&dfa_changes_vector, t_int32, 16, 1);
    root[4] = dfa_changes_vector;
    dfa_changes = dfa_changes_vector->v.i32;

    evector(&dfa_escapes_vector, t_int32, 16, 1);
    root[5] = dfa_escapes_vector;
    dfa_escapes = dfa_escapes_vector->v.i32;
}

void
finish_dfa(void)
{
    erem_root((eobject_t *)&dfa_root);
}

void
edfa(efunction_t *function)
{
    ebool_t		  loop;
    edfa_rule_t		 *rule;
    elabel_t		 *label;
    ebool_t		  global;
    eint32_t		  offset;
    elabel_t		**labels;
    eobject_t		  object;
    esymbol_t		 *symbol;
    esymbol_t		**symbols;
    eint32_t		  num_labels;
    eint32_t		  num_symbols;

    symbols = function->vsym->v.obj;
    num_symbols = function->vsym->offset;
    labels = function->labels->v.obj;
    num_labels = function->labels->offset;

    if (dfa_data->length < num_symbols)
	erenew_vector(dfa_data, num_symbols);

    loop = false;
    for (offset = 0; offset < num_labels; offset++) {
	label = labels[offset];
	if (label->loop > 1)
	    loop = true;
	if (label->dfa == null)
	    evector(&label->dfa, t_void, num_symbols, 1);
	else {
	    dfa_collect_symbols(label->dfa);
	    if (label->dfa->length != num_symbols)
		erenew_vector(label->dfa, num_symbols);
	}
    }

    if (dfa_changes_vector->length < num_symbols) {
	erenew_vector(dfa_changes_vector, (num_symbols + 15) & ~15);
	dfa_changes = dfa_changes_vector->v.i32;
	erenew_vector(dfa_escapes_vector, (num_symbols + 15) & ~15);
	dfa_escapes = dfa_escapes_vector->v.i32;
    }

    /* entry point */
    label = labels[0];
    dfa_changes_vector->offset = dfa_escapes_vector->offset = 0;
    for (offset = 0; offset < num_symbols; offset++) {
	symbol = symbols[offset];
	global = symbol->a_global && function != fn_root;
	if (!(global || symbol->a_field || symbol->offset < 0 ||
	      symbol->a_expression || symbol->offset == function->tryoff)) {
	    switch (symbol->type) {
		case t_int8:		case t_uint8:
		case t_int16:		case t_uint16:
		case t_int32:		case t_uint32:
		case t_int:		case t_uint:
		    object = ecode_int(0);
		    break;
		case t_float32:		case t_float64:
		    object = ecode_float(0.0);
		    break;
		default:
		    object = ecode_nil();
		    break;
	    }
	    rule = dfa_create_rule(label->dfa, offset, object);
	    eq_p(rule) = 1;
	}
	else
	    dfa_undef(label->dfa, offset);

	/* if an aggregate type object */
	if (mpz_tstbit(function->esc, offset)) {
	    dfa_changes[dfa_changes_vector->offset++] = offset;
	    dfa_escapes[dfa_escapes_vector->offset++] = offset;
	}
	/* if address of variable was taken */
	else if (mpz_tstbit(function->ptr, offset) ||
		/* if a global symbol or possible argument by reference
		 * or that may have a global pointer elsewhere */
		 symbol->a_field || symbol->a_global ||
		 /* special, "cosmetic", check for 'this' */
		 (symbol->name != symbol_this->name && symbol->offset < 0))
	    dfa_changes[dfa_changes_vector->offset++] = offset;
    }

    mpz_set_ui(zmsk, 0);
    dfa(label);
    if (loop) {
	/* run again to have rules in nested loops properly propagate */
	mpz_set_ui(zmsk, 0);
	dfa(label);
    }
    for (offset = 0; offset < num_labels; offset++) {
	label = labels[offset];
	dfa_eval_symbols(label->dfa, label->use);
    }
}

static void
dfa_init(elabel_t *label)
{
    if (label->stack) {
	if (dfa_value_vector->length < label->stack) {
	    erenew_vector(dfa_value_vector, dfa_value_vector->length + 16);
	    dfa_value = dfa_value_vector->v.obj;
	}
	memset(dfa_value, 0, label->stack * sizeof(eobject_t));
	dfa_value_vector->offset = label->stack;
    }
    else
	dfa_value_vector->offset = 0;

    dfa_collect_symbols(dfa_data);
    dfa_ior_symbols(label, dfa_data, label->dfa);

    if (label->sref)
	dfa_invalidate(dfa_data, dfa_changes_vector);
}

static void
dfa_value_push(east_node_t *node)
{
    if (dfa_value_vector->offset >= dfa_value_vector->length) {
	erenew_vector(dfa_value_vector, dfa_value_vector->length + 16);
	dfa_value = dfa_value_vector->v.obj;
    }
    dfa_value[dfa_value_vector->offset++] = node;
}

static void
dfa_value_pop(eint32_t count)
{
    dfa_value_vector->offset -= count;
    assert(dfa_value_vector->offset >= 0);
}

static edfa_rule_t **
dfa_get_rule_pool(eint32_t length)
{
    /* +16 to ensure at least one free entry every time, used by dfa_get_xxx */
    length = (dfa_rule_pool->offset + length + 16) & ~15;
    if (length > dfa_rule_pool->length)
	erenew_vector(dfa_rule_pool, length);

    return (dfa_rule_pool->v.obj);
}

static ehash_t **
dfa_get_hash_pool(eint32_t length)
{
    length = (dfa_hash_pool->offset + length + 16) & ~15;
    if (length > dfa_hash_pool->length)
	erenew_vector(dfa_hash_pool, length);

    return (dfa_hash_pool->v.obj);
}

static void
dfa_collect_rules(ehash_t *hash)
{
    edfa_rule_t		**pool;
    edfa_rule_t		 *rule;
    eint32_t		  offset;

    pool = dfa_get_rule_pool(hash->count);
    for (offset = 0; offset < hash->size; offset++) {
	rule = (edfa_rule_t *)hash->entries[offset];
	for (; rule; rule = rule->next)
	    pool[dfa_rule_pool->offset++] = rule;
    }
    dfa_get_hash_pool(1)[dfa_hash_pool->offset++] = hash;
    eclr_hash(hash);
}

static void
dfa_collect_symbols(evector_t *vector)
{
    ehash_t		 *hash;
    ehash_t		**hashes;
    eint32_t		  offset;

    hashes = vector->v.obj;
    for (offset = 0; offset < vector->length; offset++) {
	if ((hash = hashes[offset])) {
	    if (hash != dfa_undef_object)
		dfa_collect_rules(hashes[offset]);
	    hashes[offset] = null;
	}
    }
}

static edfa_rule_t *
dfa_get_rule(void)
{
    edfa_rule_t		**pool;
    edfa_rule_t		 *rule;

    pool = dfa_rule_pool->v.obj;
    if (dfa_rule_pool->offset) {
	rule = pool[--dfa_rule_pool->offset];
	word_p(rule) = 0;
	rule->bit = 0;
    }
    else {
	enew((eobject_t *)(pool + dfa_rule_pool->offset), dfa_rule);
	rule = pool[dfa_rule_pool->offset];
    }

    return (rule);
}

static ehash_t *
dfa_get_hash(void)
{
    ehash_t		**pool;
    ehash_t		 *hash;

    pool = dfa_hash_pool->v.obj;
    if (dfa_hash_pool->offset)
	hash = pool[--dfa_hash_pool->offset];
    else {
	enew_hash((eobject_t *)(pool + dfa_hash_pool->offset), H_pointer, 5);
	hash = pool[dfa_hash_pool->offset];
    }

    return (hash);
}

static void
dfa_eval(edfa_rule_t *rule)
{
    if (lt_p(rule) && gt_p(rule) && eq_p(rule))
	lt_p(rule) = gt_p(rule) = eq_p(rule) = 0;
}

static void
dfa_eval_rules(ehash_t *hash)
{
    edfa_rule_t		 *next;
    edfa_rule_t		**pool;
    edfa_rule_t		 *prev;
    edfa_rule_t		 *rule;
    eint32_t		  offset;

    pool = dfa_get_rule_pool(hash->count);
    for (offset = 0; offset < hash->size; offset++) {
	for (prev = rule = (edfa_rule_t *)hash->entries[offset]; rule;) {
	    next = rule->next;
	    dfa_eval(rule);
	    /* if conflicting rule */
	    if (word_p(rule) == 0) {
		pool[dfa_rule_pool->offset++] = rule;
		if (prev == rule) {
		    prev = next;
		    hash->entries[offset] = (eentry_t *)next;
		}
		else
		    prev->next = next;
		if (--hash->count == 0) {
		    dfa_get_hash_pool(1)[dfa_hash_pool->offset++] = hash;
		    return;
		}
	    }
	    else
		prev = rule;
	    rule = next;
	}
    }
}

static void
dfa_eval_symbols(evector_t *vector, empz_t mask)
{
    ehash_t		 *hash;
    ehash_t		**table;
    eint32_t		  offset;

    table = vector->v.obj;
    for (offset = 0; offset < vector->length; offset++, table++) {
	if ((hash = *table)) {
	    if (hash == dfa_undef_object)
		*table = null;
	    else {
		if (!mpz_tstbit(mask, offset)) {
		    dfa_collect_rules(*table);
		    *table = null;
		}
		else {
		    dfa_eval_rules(*table);
		    if ((*table)->count == 0)
			*table = null;
		}
	    }
	}
    }
}

static void
dfa_ior_rules(ehash_t *dst_hash, ehash_t *src_hash)
{
    eint32_t		offset;
    edfa_rule_t		*dst_rule;
    edfa_rule_t		*src_rule;

    for (offset = 0; offset < src_hash->size; offset++) {
	src_rule = (edfa_rule_t *)src_hash->entries[offset];
	for (; src_rule; src_rule = src_rule->next) {
	    dst_rule = (edfa_rule_t *)eget_hash(dst_hash, src_rule->name);
	    if (dst_rule == null) {
		dst_rule = dfa_get_rule();
		dst_rule->bit = src_rule->bit;
		dst_rule->name = src_rule->name;
		dst_rule->value = src_rule->value;
		word_p(dst_rule) = word_p(src_rule);
		eput_hash(dst_hash, (eentry_t *)dst_rule);
	    }
	    else
		word_p(dst_rule) |= word_p(src_rule);
	}
    }
}

static void
dfa_ior_symbols(elabel_t *label, evector_t *dst_vector, evector_t *src_vector)
{
    ehash_t		**dst;
    ehash_t		**src;
    eint32_t		 offset;

    dst = dst_vector->v.obj;
    src = src_vector->v.obj;
    for (offset = 0; offset < src_vector->length; offset++, dst++, src++) {
	if (*src) {
	    if (*src == dfa_undef_object) {
		if (*dst && *dst != dfa_undef_object)
		    dfa_collect_rules(*dst);
		*dst = dfa_undef_object;
	    }
	    else {
		if (*dst == dfa_undef_object)
		    continue;
		if (*dst == null)
		    *dst = dfa_get_hash();
		dfa_ior_rules(*dst, *src);
	    }
	}
    }
}

static void
dfa_clear(evector_t *vector, eint32_t bit)
{
    ehash_t		 *hash;
    ehash_t		**hashes;

    hashes = vector->v.obj;
    if ((hash = hashes[bit])) {
	if (hash != dfa_undef_object)
	    dfa_collect_rules(hash);
	hashes[bit] = null;
    }
}

static void
dfa_undef(evector_t *vector, eint32_t bit)
{
    ehash_t		 *hash;
    ehash_t		**hashes;

    hashes = vector->v.obj;
    if ((hash = hashes[bit])) {
	if (hash != dfa_undef_object) {
	    dfa_collect_rules(hash);
	    hashes[bit] = dfa_undef_object;
	}
    }
    else
	hashes[bit] = dfa_undef_object;
}

static void
dfa_define(evector_t *vector, eint32_t bit)
{
    ehash_t		 *hash;
    ehash_t		**hashes;

    hashes = vector->v.obj;
    if ((hash = hashes[bit]) && hash == dfa_undef_object)
	hashes[bit] = null;
}

static void
dfa_invalidate(evector_t *vector, evector_t *offsets)
{
    eint32_t		 *bits;
    ehash_t		 *hash;
    ehash_t		**hashes;
    eint32_t		  offset;

    bits = offsets->v.i32;
    hashes = vector->v.obj;
    for (offset = 0; offset < offsets->offset; offset++, bits++) {
	if ((hash = hashes[offset])) {
	    if (hash != dfa_undef_object) {
		dfa_collect_rules(hash);
		hashes[offset] = dfa_undef_object;
	    }
	}
    }
}

static eobject_t
dfa_canonicalize(east_node_t *node)
{
    if (node) {
	switch (node->code) {
	    case eop_ld:		case eop_ldt:
	    case eop_sd:		case eop_sdt:
	    case eop_lb:		case eop_lbt:
	    case eop_sb:		case eop_sbt:
	    case eop_lc:		case eop_sc:
		return (node->csymbol.symbol);
	    case eop_nil:		case eop_int:
	    case eop_float:		case eop_ll:
		return (node);
	    default:
		abort();
	}
    }
    return (null);
}

static edfa_rule_t *
dfa_create_rule(evector_t *vector, eint32_t offset, eobject_t value)
{
    ehash_t		 *hash;
    edfa_rule_t		 *rule;
    ehash_t		**hashes;

    assert(value != null);
    hashes = vector->v.obj;
    if ((hash = hashes[offset]) == null)
	hash = hashes[offset] = dfa_get_hash();
    else if (hash == dfa_undef_object)
	return (null);
    if ((rule = (edfa_rule_t *)eget_hash(hash, value)) == null) {
	rule = dfa_get_rule();
	rule->name = value;
	rule->value = ((esymbol_t **)fn_current->vsym->v.obj)[offset];
	eput_hash(hash, (eentry_t *)rule);
    }

    return (rule);
}

static ebool_t
dfa_rule_set(evector_t *vector, east_node_t *name, east_node_t *value)
{
    edfa_rule_t		*rule;
    eobject_t		 symbol;
    eobject_t		 object;

    symbol = dfa_canonicalize(name);
    assert(esymbol_p(symbol));

    object = dfa_canonicalize(value);

    /* may happen on inc/dec */
    if (symbol == object)
	return (false);
    if (value == null)
	dfa_undef(vector, name->csymbol.bit);
    else {
	dfa_clear(vector, name->csymbol.bit);
	rule = dfa_create_rule(vector, name->csymbol.bit, object);
	eq_p(rule) = 1;
    }

    return (true);
}

static ebool_t
dfa_add_rule(elabel_t *label, evector_t *vector,
	     east_node_t *name, east_node_t *value, eint32_t code)
{
    edfa_rule_t		*rule;
    eobject_t		 symbol;
    eobject_t		 object;

    symbol = dfa_canonicalize(name);
    assert(esymbol_p(symbol));
    object = dfa_canonicalize(value);
    if ((rule = dfa_create_rule(vector, name->csymbol.bit, object)) == null)
	return (false);

    switch (code) {
	case dfa_ne:	 lt_p(rule) = gt_p(rule) = 1;	break;
	case dfa_lt:	 lt_p(rule) = 1;		break;
	case dfa_le:	 lt_p(rule) = eq_p(rule) = 1;	break;
	case dfa_eq:	 eq_p(rule) = 1;		break;
	case dfa_ge:	 eq_p(rule) = gt_p(rule) = 1;	break;
	case dfa_gt:	 gt_p(rule) = 1;		break;
	default:	 abort();
    }

    return (true);
}

static ebool_t
dfa_add_rule_cond(elabel_t *label, evector_t *vector,
		  east_node_t *name, east_node_t *value,
		  ecode_t code, ebool_t cond, ebool_t swap)
{
    eint32_t		 rule;

    switch (code) {
	case eop_ne:
	    rule = cond ? dfa_ne : dfa_eq;
	    break;
	case eop_lt:
	    rule = cond ? (swap ? dfa_gt : dfa_lt) : (swap ? dfa_le : dfa_ge);
	    break;
	case eop_le:
	    rule = cond ? (swap ? dfa_ge : dfa_le) : (swap ? dfa_lt : dfa_gt);
	    break;
	case eop_eq:
	    rule = cond ? dfa_eq : dfa_ne;
	    break;
	case eop_ge:
	    rule = cond ? (swap ? dfa_le : dfa_ge) : (swap ? dfa_gt : dfa_lt);
	    break;
	case eop_gt:
	    rule = cond ? (swap ? dfa_lt : dfa_gt) : (swap ? dfa_ge : dfa_le);
	    break;
	default:
	    abort();
    }

    return (dfa_add_rule(label, vector, name, value, rule));
}

static void
dfa_rule_bool(elabel_t *label, east_node_t *node,
	      ecode_t code, east_node_t *jump)
{
    ebool_t		 cond;
    elabel_t		*flow;
    elabel_t		*next;
    eobject_t		 symbol;
    eobject_t		 object;

    assert(!label->ojmp);
    flow = label->next;
    next = jump->clabel.label;
    cond = jump->code == eop_jt;
    symbol = dfa_canonicalize(node);

    if (esymbol_p(symbol)) {
	dfa_define(dfa_data, node->csymbol.bit);
	dfa_ior_symbols(flow, flow->dfa, dfa_data);
	dfa_ior_symbols(next, next->dfa, dfa_data);
	object = ecode_nil();
	code = code == eop_bool ? eop_ne : eop_eq;
	dfa_add_rule_cond(flow, flow->dfa, node, object,
			  code, cond, true);
	dfa_add_rule_cond(next, next->dfa, node, object,
			  code, cond, false);
    }
    else {
	dfa_ior_symbols(flow, flow->dfa, dfa_data);
	dfa_ior_symbols(next, next->dfa, dfa_data);
    }
}

static void
dfa_rule_cond(elabel_t *label, east_node_t *lnode, east_node_t *rnode,
	      ecode_t code, east_node_t *jump)
{
    ebool_t		 cond;
    elabel_t		*flow;
    elabel_t		*next;
    eobject_t		 lvalue;
    eobject_t		 rvalue;

    assert(!label->ojmp);
    flow = label->next;
    next = jump->clabel.label;
    cond = jump->code == eop_jt;
    lvalue = dfa_canonicalize(lnode);
    rvalue = dfa_canonicalize(rnode);

    if (esymbol_p(lvalue))
	dfa_define(dfa_data, lnode->csymbol.bit);
    else if (esymbol_p(rvalue))
	dfa_define(dfa_data, rnode->csymbol.bit);

    dfa_ior_symbols(flow, flow->dfa, dfa_data);
    dfa_ior_symbols(next, next->dfa, dfa_data);

    if (esymbol_p(lvalue)) {
	dfa_add_rule_cond(flow, flow->dfa, lnode, rnode, code, !cond, false);
	dfa_add_rule_cond(next, next->dfa, lnode, rnode, code,  cond, false);
    }
    else if (esymbol_p(rvalue)) {
	dfa_add_rule_cond(flow, flow->dfa, rnode, lnode, code, !cond, true);
	dfa_add_rule_cond(next, next->dfa, rnode, lnode, code,  cond, true);
    }
}

static void
dfa_rule_table(elabel_t *label, east_node_t *name, ehash_t *table)
{
    elabel_t		*next;
    east_node_t		*node;
    eentry_t		*entry;
    eobject_t		 symbol;
    eint32_t		 offset;

    symbol = dfa_canonicalize(name);
    if (esymbol_p(symbol))
	dfa_define(dfa_data, name->csymbol.bit);

    for (offset = 0; offset < table->size; offset++) {
	for (entry = table->entries[offset]; entry; entry = entry->next) {
	    if (entry->name == null)
		continue;
	    node = entry->value;
	    next = node->clabel.label;
	    dfa_ior_symbols(next, next->dfa, dfa_data);
	    if (esymbol_p(symbol))
		dfa_add_rule(next, next->dfa, name,
			     ecode_int(eget_integer(entry->name)),
			     dfa_eq);
	}
    }
}

static void
dfa_body(elabel_t *label)
{
    ecode_t		 code;
    east_list_t		*list;
    east_node_t		*node;
    elabel_t		*next;
    east_node_t		*lnode;
    east_node_t		*rnode;
    eint32_t		 state;
    eint32_t		 offset;
    efunction_t		*lambda;

#define have_none	0
#define have_lnode	1
#define wait_rnode	2
#define have_rnode	4
#define have_unary	5
#define have_binary	6

    code = eop_noop;
    state = have_none;
    lnode = rnode = null;
    for (list = east_next(label->list); list; list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_label:		case eop_block:
		if (!label->ojmp) {
		    next = node->clabel.label;
		    dfa_ior_symbols(next, next->dfa, dfa_data);
		}
		return;
	    case eop_nil:		case eop_int:
	    case eop_float:		case eop_ll:
	    case eop_ld:		case eop_lb:
	    case eop_ldt:		case eop_lbt:
	    case eop_lc:
	    argument:
		if (state == wait_rnode) {
		    rnode = node;
		    state = have_rnode;
		}
		else {
		    lnode = node;
		    state = have_lnode;
		}
		break;
	    case eop_ls:
		offset = dfa_value_vector->offset + node->cstack.offset;
		assert(offset >= 0 && offset < dfa_value_vector->offset);
		if ((node = dfa_value[offset]))
		    goto argument;
		state = have_none;
		break;
	    case eop_lh:		case eop_and:
	    case eop_or:		case eop_xor:
	    case eop_mul2:		case eop_div2:
	    case eop_trunc2:		case eop_shl:
	    case eop_shr:		case eop_add:
	    case eop_sub:		case eop_mul:
	    case eop_div:		case eop_rem:
	    case eop_atan2:		case eop_pow:
	    case eop_complex:		case eop_hypot:
	    case eop_szofdim:
	    case eop_subtpof:
		state = have_none;
		dfa_value_pop(1);
		break;
	    case eop_mv:		case eop_vmv:
	    case eop_renew:
		state = have_none;
		dfa_value_pop(1);
		dfa_invalidate(dfa_data, dfa_escapes_vector);
		break;
	    case eop_lhref:
		state = have_none;
		if (node->chash.arg)
		    dfa_value_push(null);
		break;
	    case eop_lv:		case eop_pv:
		state = have_none;
		dfa_value_pop(node->cvector.rank);
		break;
	    case eop_lvi:		case eop_lr:
	    case eop_lref:		case eop_pdt:
	    case eop_pbt:		case eop_pd:
	    case eop_pb:		case eop_pvi:
	    case eop_pr:		case eop_pp:
	    case eop_anon:		case eop_enter:
	    case eop_ret:		case eop_reti:
	    case eop_rett:		case eop_retit:
	    case eop_com:		case eop_floor:
	    case eop_trunc:		case eop_round:
	    case eop_ceil:		case eop_den:
	    case eop_neg:		case eop_inv:
	    case eop_integer_p:		case eop_rational_p:
	    case eop_float_p:		case eop_real_p:
	    case eop_complex_p:		case eop_number_p:
	    case eop_finite_p:		case eop_inf_p:
	    case eop_nan_p:		case eop_signbit:
	    case eop_signum:		case eop_rational:
	    case eop_num:		case eop_real:
	    case eop_imag:		case eop_arg:
	    case eop_conj:		case eop_abs:
	    case eop_sqrt:		case eop_cbrt:
	    case eop_sin:		case eop_cos:
	    case eop_tan:		case eop_asin:
	    case eop_acos:		case eop_atan:
	    case eop_sinh:		case eop_cosh:
	    case eop_tanh:		case eop_asinh:
	    case eop_acosh:		case eop_atanh:
	    case eop_proj:		case eop_exp:
	    case eop_log:		case eop_log2:
	    case eop_log10:		case eop_new:
	    case eop_vnewi:		case eop_renewi:
	    case eop_fref:		case eop_szof:
	    case eop_szofva:		case eop_szofdimi:
	    case eop_tpof:		case eop_rankof:
	    case eop_lva:		case eop_lvai:
	    case eop_pva:		case eop_intp_v:
	    case eop_realp_v:		case eop_nump_v:
	    case eop_throw:
		state = have_none;
		break;
	    case eop_bool:		case eop_not:
		if (state == have_lnode) {
		    state = have_unary;
		    code = node->code;
		}
		else
		    state = have_none;
		break;
	    case eop_lvref:
		state = have_none;
		dfa_value_pop(node->cvector.rank - 1);
		if (node->cvector.arg)
		    dfa_value_push(null);
		break;
	    case eop_lrref:
		state = have_none;
		dfa_value_push(null);
		if (node->crecord.arg)
		    dfa_value_push(null);
		break;
	    case eop_sd:		case eop_sb:
	    case eop_sc:		case eop_sdt:
	    case eop_sbt:
		if (state == have_lnode || state == wait_rnode)
		    dfa_rule_set(dfa_data, node, lnode);
		else if (state == have_rnode)
		    dfa_rule_set(dfa_data, node, rnode);
		else {
		    dfa_rule_set(dfa_data, node, null);
		    if (state == have_none && !node->csymbol.symbol->type)
			goto argument;
		}
		break;
	    case eop_ss:		case eop_ssv:
	    case eop_sst:
		offset = dfa_value_vector->offset + node->cstack.offset;
		assert(offset >= 0 && offset < dfa_value_vector->offset);
		if (state == have_lnode || state == wait_rnode)
		    dfa_value[offset] = lnode;
		else if (state == have_rnode)
		    dfa_value[offset] = rnode;
		else {
		    state = have_none;
		    dfa_value[offset] = null;
		}
		break;
	    case eop_sh:
		state = have_none;
		dfa_value_pop(2);
		dfa_invalidate(dfa_data, dfa_escapes_vector);
		break;
	    case eop_shref:
		state = have_none;
		dfa_value_pop(!!node->chash.arg + 1);
		break;
	    case eop_sv:
		state = have_none;
		dfa_value_pop(node->cvector.rank + 1);
		dfa_invalidate(dfa_data, dfa_escapes_vector);
		break;
	    case eop_svi:		case eop_sr:
		state = have_none;
		dfa_value_pop(1);
		dfa_invalidate(dfa_data, dfa_escapes_vector);
		break;
	    case eop_sref:
		state = have_none;
		dfa_value_pop(1);
		dfa_invalidate(dfa_data, dfa_changes_vector);
		break;
	    case eop_svref:
		state = have_none;
		dfa_value_pop(!!node->cvector.arg + 1);
		break;
	    case eop_srref:
		state = have_none;
		dfa_value_pop(!!node->crecord.arg + 1);
		break;
	    case eop_jt:		case eop_jf:
		if (state == have_binary)
		    dfa_rule_cond(label, lnode, rnode, code, node);
		else if (state == have_lnode)
		    dfa_rule_bool(label, lnode, eop_bool, node);
		else if (state == have_unary)
		    dfa_rule_bool(label, lnode, code, node);
#if DEBUG
		if ((list = east_next(list))) {
		    node = east_node(list);
		    assert(node->code == eop_label || node->code == eop_block);
		}
#endif
		return;
	    case eop_j:
		next = node->clabel.label;
		dfa_ior_symbols(next, next->dfa, dfa_data);
		state = have_none;
		return;
	    case eop_jh:
		if (state == have_lnode)
		    dfa_rule_table(label, lnode, els[immediate_offset(node)]);
		state = have_none;
		break;
	    case eop_begin:
		state = have_none;
		for (offset = node->cstack.length; offset; offset--)
		    dfa_value_push(null);
		break;
	    case eop_off:
		state = have_none;
		dfa_value_push(null);
		break;
	    case eop_push:
		if (state == have_lnode &&
		    node->cstack.flags & code_stack_binarg) {
		    state = wait_rnode;
		    dfa_value_push(lnode);
		}
		else {
		    state = have_none;
		    dfa_value_push(null);
		}
		break;
	    case eop_pushv:			case eop_pusht:
		state = have_none;
		dfa_value_push(null);
		break;
	    case eop_pop:
		dfa_value_pop(1);
		if ((node = dfa_value[dfa_value_vector->offset]))
		    goto argument;
		state = have_none;
		break;
	    case eop_call:			case eop_ecm:
		state = have_none;
		dfa_value_pop(node->capply.length);
		lambda = node->capply.symbol->value;
		if (!cfg_pass || lambda->flags)
		    dfa_invalidate(dfa_data, dfa_changes_vector);
		break;
	    case eop_blt:
		state = have_none;
		dfa_value_pop(node->capply.length);
		if (!cfg_pass || (fn_current->flags & fun_esc))
		    dfa_invalidate(dfa_data, dfa_changes_vector);
		break;
	    case eop_meth:			case eop_apply:
		state = have_none;
		dfa_value_pop(node->capply.length);
		dfa_invalidate(dfa_data, dfa_changes_vector);
		break;
	    case eop_ne:			case eop_lt:
	    case eop_le:			case eop_eq:
	    case eop_ge:			case eop_gt:
		if (state == have_rnode) {
		    state = have_binary;
		    code = node->code;
		}
		else
		    state = have_none;
		dfa_value_pop(1);
		break;
	    case eop_inc:			case eop_dec:
		/* do nothing */
		break;
	    case eop_vnew:
		state = have_none;
		dfa_value_pop(node->cvector.rank - 1);
		break;
	    case eop_aret:			case eop_vas:
	    case eop_svai:			case eop_exit:
	    case eop_setup:			case eop_note:
		break;
	    case eop_val:
		state = have_none;
		dfa_value_pop(node->cstack.length);
		break;
	    case eop_sva:
		state = have_none;
		dfa_value_pop(1);
		break;
	    case eop_try:
		state = have_none;
		dfa_value_push(null);
		dfa_value_push(null);
		dfa_value_push(null);
		dfa_value_push(null);
		break;
	    case eop_catch:
		state = have_none;
		assert(label->stack == dfa_value_vector->offset);
		dfa_value_pop(4);
		break;
	    case eop_unwind:
		state = have_none;
		if (node->cexcept.arg)
		    dfa_value_pop(4);
		break;
	    case eop_intp_0:		case eop_nump_0:
		node = ecode_int(0);
		goto argument;
	    case eop_intp_n1:
		node = ecode_int(-1);
		goto argument;
	    default:
		abort();
	}
    }
}

static void
dfa(elabel_t *label)
{
    elabel_t		**labels;
    eint32_t		  offset;

    /* parse only once */
    if (mpz_tstbit(zmsk, label->ident))
	return;
    mpz_setbit(zmsk, label->ident);

    /* resolve incoming rules */
    labels = label->srcs->v.obj;
    for (offset = 0; offset < label->srcs->offset; offset++)
	dfa(labels[offset]);

    dfa_init(label);
    dfa_body(label);

    /* resolve destination rules */
    labels = label->dsts->v.obj;
    for (offset = 0; offset < label->dsts->offset; offset++)
	dfa(labels[offset]);
}
